﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo.Algorithms
{
    /// <summary>
    /// 遍历接口
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface ITraversable<T>
    {
        IEnumerable<T> GetTraveller(T start);
    }

    /// <summary>
    /// 记录访问路线的遍历接口
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IRoutingTraversable<T> : ITraversable<T>
    {
        IEnumerable<T> GetTraveller(T start, Dictionary<T, T> routes);
    }

    public delegate IEnumerable<T> TravelHandler<T>(T start);
    public delegate IEnumerable<T> RoutingTravelHandler<T>(T start, Dictionary<T, T> routes);


    /// <summary>
    /// 记录访问路线的遍历基类
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public abstract class RoutingTravel<T> : IRoutingTraversable<T>
    {
        protected RoutingTravel(TravelHandler<T> subsTravelling)
        {
            SubsTravelling = subsTravelling;
        }

        public readonly TravelHandler<T> SubsTravelling;
        public abstract IEnumerable<T> GetTraveller(T start, Dictionary<T, T> routes);

        public IEnumerable<T> GetTraveller(T start)
        {
            return GetTraveller(start, new Dictionary<T, T>());
        }
        public virtual T[] GetShortestPath(T start, T end)
        {
            Dictionary<T, T> routes = new Dictionary<T, T>();
            List<T> list = new List<T>();
            foreach (T t in GetTraveller(start, routes))
            {
                if(end.Equals(t))
                {
                    while (!end.Equals(start))
                    {
                        list.Add(end);
                        end = routes[end];
                    }
                    list.Add(end);
                    list.Reverse();
                    break;
                }
            }
            return list.ToArray();
        }
    }

    /// <summary>
    /// 广度优先遍历
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BFS<T> : RoutingTravel<T>
    {
        public BFS(TravelHandler<T> subsTravelling)
            :base(subsTravelling)
        {}
        public override IEnumerable<T> GetTraveller(T start, Dictionary<T, T> routes)
        {
            Queue<T> q = new Queue<T>();
            q.Enqueue(start);
            routes.Add(start, start);
            yield return start;
            do
            {
                T t = q.Dequeue();
                foreach (T t1 in SubsTravelling(t))
                {
                    if (!routes.ContainsKey(t1))
                    {
                        q.Enqueue(t1);
                        routes.Add(t1, t);
                        yield return t1;
                    }
                }
            } while (q.Count > 0);
        }
    }

    /// <summary>
    /// 深度优先遍历
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class DFS<T> : RoutingTravel<T>
    {
        public DFS(TravelHandler<T> subsTravelling)
            :base(subsTravelling)
        {}

        public override IEnumerable<T> GetTraveller(T start, Dictionary<T, T> routes)
        {
            Stack<T> s = new Stack<T>();
            Stack<IEnumerator<T>> se = new Stack<IEnumerator<T>>();
            s.Push(start);
            se.Push(SubsTravelling(start).GetEnumerator());
            routes.Add(start, start);
            yield return start;
            do
            {
                T t = s.Peek();
                IEnumerator<T> e = se.Peek();
            Loop:
                if(e.MoveNext())
                {
                    if (!routes.ContainsKey(e.Current))
                    {
                        T t1 = e.Current;
                        s.Push(t1);
                        se.Push(SubsTravelling(t1).GetEnumerator());
                        routes.Add(t1, t);
                        yield return t1;
                    }
                    else
                        goto Loop;
                }
                else
                {
                    s.Pop();
                    se.Pop();
                }
            } while (se.Count > 0);
        }
    }
}
